package com.zyk.grate_offer.class03;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 力扣： https://leetcode-cn.com/problems/freedom-trail/
 *
 * @author zhangsan
 * @date 2021/4/28 14:59
 */
public class Code07_FreedomTrail {


    public static int findRotateSteps(String ring, String key) {
        char[] str = ring.toCharArray();
        int N = str.length;
        Map<Character, List<Integer>> cMap = new HashMap<>();   // 字符对应顺序表
        for (int i = 0; i < N; i++) {
            if (!cMap.containsKey(str[i])) {
                cMap.put(str[i], new ArrayList<>());
            }
            cMap.get(str[i]).add(i);
        }
        int[][] dp = new int[N][key.length() + 1];
        return process(0, 0, key.toCharArray(), cMap, N, dp);
    }

    /**
     * dfs尝试
     *
     * @param curIndex 当前所在轮盘位置
     * @param i        当前要搞定的字符
     * @param str      字符
     * @param cMap     辅助表： 存放轮盘的字符都在哪儿些位置出现
     * @param dp
     * @return 最少的步数
     */
    public static int process(int curIndex, int i, char[] str, Map<Character, List<Integer>> cMap, int N, int[][] dp) {
        if (dp[curIndex][i] != 0) return dp[curIndex][i];
        if (i == str.length) return 0;
        List<Integer> nextPosition = cMap.get(str[i]);
        int ans = Integer.MAX_VALUE;
        for (int next : nextPosition) {
            int step = process(next, i + 1, str, cMap, N, dp) + step(curIndex, next, N) + 1;
            ans = Math.min(ans, step);
        }
        dp[curIndex][i] = ans;
        return ans;
    }

    // 0 ~ N 是个环形，N后追0.     求从i走到j的步数（最少的）
    public static int step(int i, int j, int N) {
//        int p1 = Math.abs(i - j);   // 下标直接减
//        int p2 = N - Math.max(i, j) + Math.min(i, j);
        return Math.min(Math.abs(i - j), N - Math.max(i, j) + Math.min(i, j));
    }


    // for test
    public static void main(String[] args) {
//        System.out.println(step(1, 4, 6));


        String ring = "godding";
        String key = "gd";
        System.out.println(findRotateSteps(ring, key));
    }

}
